/**
 * Title: Hyperbolic engine
 * Description: jFamilyTree Engine
 * Version: provider
 * Copyright: (c) 2001-2008
 * Terms of use:see license agreement at http://treebolic.sourceforge.net/en/license.htm
 * Author: Bernard Bou
 * Company: bsys
 * Update: Mon Mar 10 00:00:00 CEST 2008
 */
package jFamilyTree.view;

import java.awt.BasicStroke;
import java.awt.Color;
import java.awt.Dimension;
import java.awt.Font;
import java.awt.FontMetrics;
import java.awt.Graphics2D;
import java.awt.Image;
import java.awt.RenderingHints;
import java.awt.Stroke;
import java.awt.geom.AffineTransform;
import java.awt.geom.Arc2D;
import java.awt.geom.Point2D;
import java.awt.geom.Rectangle2D;
import java.awt.geom.RoundRectangle2D;
import java.util.List;

import jFamilyTree.core.Arc;
import jFamilyTree.core.Complex;
import jFamilyTree.model.IEdge;
import jFamilyTree.model.INode;
import jFamilyTree.model.Location;
import jFamilyTree.model.MountPoint;

/**
 * Painter class
 * 
 * @author Bernard Bou
 */
public class Painter extends AbstractPainter
{
	// C O N S T A N T S

	/**
	 * Dot pattern
	 */
	static private final float[] theDotPattern = { 1, 3 };

	/**
	 * Dot stroke
	 */
	static private final BasicStroke theDotStroke = new BasicStroke(1.0F, BasicStroke.CAP_BUTT, BasicStroke.JOIN_BEVEL, 10.0F, theDotPattern, 0);

	/**
	 * Dash pattern
	 */
	static private final float[] theDashPattern = { 10, 4 };

	/**
	 * Dash stroke
	 */
	static private final BasicStroke theDashStroke = new BasicStroke(1.0F, BasicStroke.CAP_BUTT, BasicStroke.JOIN_BEVEL, 10.0F, theDashPattern, 0);

	/**
	 * Minimum span for terminators
	 */
	static private final int theMinSpanForTerminators = 50 * 50;

	/**
	 * Text padding
	 */
	static private final int theTextPadding = 25;

	/**
	 * Edge terminator length
	 */
	static private final double theTerminorLength = 8;

	/**
	 * Edge terminator width
	 */
	static private final double theTerminatorWidth = 5;

	/**
	 * Debug flag, bit1=draw circles, bit2=suppress
	 */
	static private final int theDebugFlag = 0;

	// B A C K G R O U N D

	/*
	 * (non-Javadoc)
	 * 
	 * @see jFamilyTree.view.AbstractPainter#paintBackground()
	 */
	public void paintBackground()
	{
		theGraphics.setColor(theBackColor);
		theGraphics.fillRect(theLeft, theTop, theSize.width, theSize.height);
		theGraphics.setPaintMode();

		if (theBackgroundImage != null)
		{
			int xinc = theBackgroundImage.getWidth(null);
			int yinc = theBackgroundImage.getHeight(null);
			if (xinc <= 0 || yinc <= 0)
				return;

			int xmax = (int) theSize.width;
			int ymax = (int) theSize.height;
			for (int y = theTop; y < ymax; y += yinc)
			{
				for (int x = theLeft; x < xmax; x += xinc)
					theGraphics.drawImage(theBackgroundImage, x, y, null);
			}
		}

		// boundary circle
		if (Painter.theDebugFlag != 0)
			drawCircle(0., 0., 1., Color.lightGray);
	}

	// D R A W

	/*
	 * (non-Javadoc)
	 * 
	 * @see jFamilyTree.view.AbstractPainter#paint(jFamilyTree.model.INode, jFamilyTree.model.IEdgeList)
	 */
	public void paint(INode thisRoot, List<IEdge> thisEdgeList)
	{
		// anti aliasing
		Graphics2D thisGraphics2 = (Graphics2D) theGraphics;
		thisGraphics2.setRenderingHint(RenderingHints.KEY_ANTIALIASING, RenderingHints.VALUE_ANTIALIAS_ON);

		// compute node data
		computeTree(thisRoot);

		// edges
		if (thisEdgeList != null)
		{
			for (IEdge thisEdge : thisEdgeList)
				draw(thisEdge);
		}

		// tree
		drawTree(thisRoot);
	}

	/**
	 * Compute tree recursively
	 * 
	 * @param thisNode
	 *        starting node
	 */
	private void computeTree(INode thisNode)
	{
		if (thisNode == null)
			return;

		// hyper circle
		Location thisLocation = thisNode.getLocation();
		if (thisLocation.hyper.isDirty)
			thisLocation.mapToUnitCircle();

		// node data and attach to node
		NodeData thisNodeData = computeNodeData(thisNode);
		thisNode.getLocation().theViewData = thisNodeData;

		// recurse to compute the children
		List<INode> theseChildren = thisNode.getChildren();
		if (theseChildren != null)
			for (INode thisChild : theseChildren)
				computeTree(thisChild);
	}

	/**
	 * Draw tree recursively
	 * 
	 * @param thisNode
	 *        starting node
	 */
	private void drawTree(INode thisNode)
	{
		if (thisNode == null)
			return;

		// edge to parent
		INode thisParent = thisNode.getParent();
		if (thisParent != null)
		{
			// color
			Color thisColor = thisNode.getEdgeColor();
			if (thisColor == null)
				thisColor = theTreeEdgeColor;
			theGraphics.setColor(thisColor);

			// draw
			drawTreeEdge(thisParent, thisNode);
		}

		// recurse to draw the children
		List<INode> theseChildren = thisNode.getChildren();
		if (theseChildren != null)
			for (INode thisChild : theseChildren)
				drawTree(thisChild);

		// debug
		if ((theDebugFlag & 1) != 0)
			drawSpace(thisNode);

		if ((theDebugFlag & 2) != 0)
			return;

		// draw node
		Location thisLocation = thisNode.getLocation();
		if (!thisLocation.hyper.isBorder)
			drawNode((NodeData) thisNode.getLocation().theViewData);
	}

	// D R A W . N O D E

	/**
	 * Class collecting drawing data
	 * 
	 * @author Bernard Bou
	 */
	private class NodeData
	{
		/**
		 * Node box
		 */
		public Rectangle2D theBox;

		/**
		 * Node label
		 */
		public String theLabel;

		/**
		 * Node label x coordinate
		 */
		public int theLabelX;

		/**
		 * Node label y coordinate
		 */
		public int theLabelY;

		/**
		 * Node image
		 */
		public Image theImage;

		/**
		 * Node image x-coordinate
		 */
		public int theImageX;

		/**
		 * Node image y-coordinate
		 */
		public int theImageY;

		/**
		 * Node backcolor
		 */
		public Color theBackColor;

		/**
		 * Node forecolor
		 */
		public Color theForeColor;

		/**
		 * Node font
		 */
		public Font theFont;

		/**
		 * Is mountable
		 */
		public Boolean isMountable;
	}

	/**
	 * Draw node
	 * 
	 * @param thisNodeData
	 *        computed node data
	 */

	private void drawNode(NodeData thisNodeData)
	{
		if (thisNodeData == null)
			return;

		// box
		if (thisNodeData.theBox != null)
		{
			// graphics context
			Graphics2D thisGraphics2 = (Graphics2D) theGraphics;

			// rectangle
			RoundRectangle2D thisRoundRectangle = new RoundRectangle2D.Double();
			thisRoundRectangle.setRoundRect(thisNodeData.theBox.getX(), thisNodeData.theBox.getY(), thisNodeData.theBox.getWidth(), thisNodeData.theBox.getHeight(), 10, 10);

			// fill
			thisGraphics2.setColor(thisNodeData.theBackColor);
			thisGraphics2.fill(thisRoundRectangle);

			// outline
			thisGraphics2.setColor(thisNodeData.theForeColor);
			thisGraphics2.draw(thisRoundRectangle);

			// mount clue
			if (thisNodeData.isMountable != null)
			{
				final int w = 3;
				final int h = 2 * w;
				final int hm = 2;
				int x = (int) thisRoundRectangle.getX() + (int) thisRoundRectangle.getWidth() + 5;
				int x1 = x - w;
				int x2 = x + w;
				int y = (int) thisRoundRectangle.getY() + hm;
				int xs[] = { x1, x, x2 };
				if (thisNodeData.isMountable)
				{
					int hr = (int) thisRoundRectangle.getHeight() - 2 * hm;
					int y2 = y + hr;
					int y1 = y2 - h;
					int ys[] = { y1, y2, y1 };
					thisGraphics2.fillPolygon(xs, ys, 3);
				}
				else
				{
					int y1 = y + h;
					int ys[] = { y1, y, y1 };
					thisGraphics2.fillPolygon(xs, ys, 3);
				}
			}
		}

		// image
		if (thisNodeData.theImage != null)
			theGraphics.drawImage(thisNodeData.theImage, thisNodeData.theImageX, thisNodeData.theImageY, null);

		// label
		if (thisNodeData.theLabel != null)
		{
			theGraphics.setFont(thisNodeData.theFont);
			theGraphics.drawString(thisNodeData.theLabel, thisNodeData.theLabelX, thisNodeData.theLabelY);
		}
	}

	/**
	 * Compute node data
	 * 
	 * @param thisNode
	 *        node
	 * @return node data
	 */
	private NodeData computeNodeData(INode thisNode)
	{
		NodeData thisNodeData = new NodeData();

		// hyper circle
		Location thisLocation = thisNode.getLocation();
		if (thisLocation.hyper.isBorder)
			return null;

		// font size
		int thisFontIdx = (int) Math.round(thisLocation.hyper.dist * NFONTS);
		thisFontIdx = Math.min(theFonts.length - 1, thisFontIdx);
		thisNodeData.theFont = theFonts[thisFontIdx];
		theGraphics.setFont(theFonts[thisFontIdx]);

		// color
		thisNodeData.theBackColor = thisNode.getBackColor();
		if (thisNodeData.theBackColor == null)
			thisNodeData.theBackColor = theNodeBackColor;
		thisNodeData.theForeColor = thisNode.getForeColor();
		if (thisNodeData.theForeColor == null)
			thisNodeData.theForeColor = theNodeForeColor;

		// center
		int x = xUnitCircleToView(thisLocation.euclidian.center.re);
		int y = yUnitCircleToView(thisLocation.euclidian.center.im);

		// node space actual diameter
		int rad = wUnitCircleToView(thisLocation.euclidian.radius);
		int dia = 2 * rad;
		int span = dia;

		// image
		thisNodeData.theImage = thisNode.getImage();
		if (thisNodeData.theImage == null)
			thisNodeData.theImage = theDefaultNodeImage;

		// string
		thisNodeData.theLabel = thisNode.toString();
		if (thisNodeData.theLabel == null || thisNodeData.theLabel.isEmpty())
		{
			if (thisNodeData.theImage != null)
			{
				int hi = thisNodeData.theImage.getHeight(null);
				int xi = x - thisNodeData.theImage.getWidth(null) / 2;
				int yi = y - hi / 2;

				thisNodeData.theImageX = xi;
				thisNodeData.theImageY = yi;
			}
			return thisNodeData;
		}

		// label font size
		FontMetrics fm = theGraphics.getFontMetrics();
		int h = fm.getAscent() /* +fm.getDescent() */;
		int w = fm.stringWidth(thisNodeData.theLabel);

		// truncate label
		if (w > span)
		{
			// compute average character width
			int wunit = fm.stringWidth("x");

			// compute trailing dots width
			int wdots = fm.stringWidth("...");

			// compute number of characters that fit before dots
			int thisNChars = (span - wdots) / wunit;

			// ensure at least one
			if (thisNChars < 1)
				thisNChars = 1;

			// perform truncation if we actually truncate
			int thisLen = thisNodeData.theLabel.length();
			if (thisLen > thisNChars)
			{
				thisNodeData.theLabel = thisNodeData.theLabel.substring(0, thisNChars) + "...";
				w = fm.stringWidth(thisNodeData.theLabel);
			}
		}

		// box computation
		int xr = (x - w / 2) - theXInset;
		int yr = (y - h / 2) - theYInset;
		int wr = w + 2 * theXInset;
		int hr = h + 2 * theYInset;

		// image computation
		int hi2 = 0; // height image
		int rs = 0; // rectangle shift
		if (thisNodeData.theImage != null)
		{
			hi2 = thisNodeData.theImage.getHeight(null) / 2;
			rs = (hi2 > rad) ? rad : hi2; // limit shift to radius
			yr += rs;
		}

		// box
		thisNodeData.theBox = new Rectangle2D.Double(xr, yr, wr, hr);

		// image
		if (thisNodeData.theImage != null)
		{
			int xi = x - thisNodeData.theImage.getWidth(null) / 2;
			int yi = y - hi2;
			thisNodeData.theImageX = xi;
			thisNodeData.theImageY = yi;
		}

		// label
		thisNodeData.theLabelX = xr + theXInset;
		thisNodeData.theLabelY = yr + theYInset + h;

		// is mountable
		MountPoint thisMountPoint = thisNode.getMountPoint();
		thisNodeData.isMountable = thisMountPoint == null ? null : thisMountPoint instanceof MountPoint.Mounting ? true : false;

		return thisNodeData;
	}

	// D R A W . E D G E

	/**
	 * Draw tree edge, from parent to child
	 * 
	 * @param thisParent
	 *        from-node
	 * @param thisNode
	 *        to-node
	 */
	private void drawTreeEdge(INode thisParent, INode thisNode)
	{
		// style
		Integer thatStyle = thisNode.getEdgeStyle();
		int thisStyle = thatStyle != null ? thatStyle : theTreeEdgeStyle;
		if ((thisStyle & IEdge.HIDDEN) != 0)
			return;

		// hyper circles
		Location thisFrom = thisParent.getLocation();
		Location thisTo = thisNode.getLocation();

		// data
		NodeData thisFromData = (NodeData) thisParent.getLocation().theViewData;
		NodeData thisToData = (NodeData) thisNode.getLocation().theViewData;
		Rectangle2D thisFromBox = thisFromData == null ? null : thisFromData.theBox;
		Rectangle2D thisToBox = thisToData == null ? null : thisToData.theBox;

		// do not draw edge if boxes intersect
		if (boxesIntersect(thisFromBox, thisToBox))
			return;

		// image
		Image thisImage = thisNode.getEdgeImage();
		if (thisImage == null)
			thisImage = theDefaultTreeEdgeImage;

		// draw
		String thisLabel = thisNode.getEdgeLabel();
		boolean isBorder = thisFrom.hyper.isBorder;
		drawArc(thisFrom.euclidian.center, thisTo.euclidian.center, thisLabel, thisImage, thisStyle, thisFromBox, thisToBox, isBorder);
	}

	/**
	 * Draw non-tree edge
	 * 
	 * @param thisEdge
	 *        edge
	 */
	private void draw(IEdge thisEdge)
	{
		// style
		Integer thatStyle = thisEdge.getStyle();
		int thisStyle = thatStyle != null ? thatStyle : theEdgeStyle;
		if ((thisStyle & IEdge.HIDDEN) != 0)
			return;

		// hyper circles
		INode thisFromNode = thisEdge.getFrom();
		INode thisToNode = thisEdge.getTo();
		if (thisFromNode == null || thisToNode == null)
			return;

		Location thisFromLocation = thisFromNode.getLocation();
		Location thisToLocation = thisToNode.getLocation();
		if (thisFromLocation.hyper.isBorder || thisToLocation.hyper.isBorder)
			return;

		if (thisFromLocation.hyper.isDirty)
			thisFromLocation.mapToUnitCircle();
		if (thisToLocation.hyper.isDirty)
			thisToLocation.mapToUnitCircle();

		// data
		NodeData thisFromData = (NodeData) thisFromNode.getLocation().theViewData;
		NodeData thisToData = (NodeData) thisToNode.getLocation().theViewData;
		if (thisFromData == null || thisToData == null)
			return;

		// do not draw edge if boxes intersect
		if (boxesIntersect(thisFromData.theBox, thisToData.theBox))
			return;

		// label
		String thisLabel = thisEdge.getLabel();
		if (thisLabel != null)
		{
			// font size
			int thisFontIdx = (int) Math.round(thisToLocation.hyper.dist * NFONTS);
			thisFontIdx = Math.min(theFonts.length - 1, thisFontIdx);
			theGraphics.setFont(theFonts[thisFontIdx]);
		}

		// draw
		Color thisColor = thisEdge.getColor();
		if (thisColor == null)
			thisColor = theEdgeColor;
		theGraphics.setColor(thisColor);

		// image
		Image thisImage = thisEdge.getImage();
		if (thisImage == null)
			thisImage = theDefaultEdgeImage;

		// draw arc
		drawArc(thisFromLocation.euclidian.center, thisToLocation.euclidian.center, thisLabel, thisImage, thisStyle, thisFromData.theBox, thisToData.theBox, false);
	}

	// D R A W . A R C

	/**
	 * Draw geodesic arc from z1 to z2 which models line from z1 to z2
	 * 
	 * @param z1
	 *        from-end
	 * @param z2
	 *        to-end
	 * @param thisLabel
	 *        arc label
	 * @param thisImage
	 *        arc image
	 * @param thisStyle
	 *        code for edge style
	 * @param thisFromBox
	 *        from-node box
	 * @param thisToBox
	 *        to-node box
	 * @param isBorder
	 *        true if arc neighbours border
	 */
	private void drawArc(Complex z1, Complex z2, String thisLabel, Image thisImage, int thisStyle, Rectangle2D thisFromBox, Rectangle2D thisToBox, boolean isBorder)
	{
		if (!hyperbolicEdges || isDragging)
		{
			Point2D thisFrom = new Point2D.Double(xUnitCircleToView(z1.re), yUnitCircleToView(z1.im));
			Point2D thisTo = new Point2D.Double(xUnitCircleToView(z2.re), yUnitCircleToView(z2.im));

			drawLine(thisFrom, thisTo, thisStyle);
			if (!isBorder && thisLabel != null && !thisLabel.isEmpty())
			{
				// fit
				thisLabel = mangleString(thisLabel, thisFrom, thisTo);
				if (thisLabel == null)
					return;

				// draw
				drawText(thisLabel, thisFrom, thisTo);
			}
		}
		else
		{
			Arc thisArc = new Arc(z1, z2);
			draw(thisArc, thisLabel, thisImage, thisStyle, thisFromBox, thisToBox, isBorder);
		}
	}

	/**
	 * Draw arc
	 * 
	 * @param thisArc
	 *        arc
	 * @param thisLabel
	 *        arc label
	 * @param thisImage
	 *        arc image
	 * @param isBorder
	 *        true if arc neighbours border
	 */
	private void draw(Arc thisArc, String thisLabel, Image thisImage, int thisStyle, Rectangle2D thisFromBox, Rectangle2D thisToBox, boolean isBorder)
	{
		// if(r == 0.) it is segment of line
		if (thisArc.r == 0.)
		{
			Point2D thisFrom = new Point2D.Double(xUnitCircleToView(thisArc.from.re), yUnitCircleToView(thisArc.from.im));
			Point2D thisTo = new Point2D.Double(xUnitCircleToView(thisArc.to.re), yUnitCircleToView(thisArc.to.im));

			// adjust to anchors
			Point2D thisFromAnchor = null;
			if (!isBorder)
				thisFromAnchor = getIntersection(thisFromBox, thisTo, thisFrom);
			Point2D thisToAnchor = null;
			thisToAnchor = getIntersection(thisToBox, thisFrom, thisTo);

			// adjust line ends
			if (thisFromAnchor != null)
				thisFrom = thisFromAnchor;
			if (thisToAnchor != null)
				thisTo = thisToAnchor;

			// line
			drawLine(thisFrom, thisTo, thisStyle);

			// image
			if (thisImage != null && !isBorder)
				drawImage(thisImage, getMiddle(thisFrom, thisTo));

			// ends
			drawEdgeEnds(thisFrom, thisTo, null, thisStyle);

			// label
			if (!isBorder && thisLabel != null && !thisLabel.isEmpty())
			{
				// fit
				thisLabel = mangleString(thisLabel, thisFrom, thisTo);
				if (thisLabel == null)
					return;

				drawText(thisLabel, thisFrom, thisTo);
			}
		}
		else
		{
			Arc2D thisArc2D = toArc2D(thisArc);

			// anchors
			Point2D thisFromAnchor = null;
			if (!isBorder)
				thisFromAnchor = getIntersection(thisFromBox, thisArc2D);
			if (thisFromAnchor == null)
				thisFromAnchor = thisArc2D.getStartPoint();

			Point2D thisToAnchor = null;
			thisToAnchor = getIntersection(thisToBox, thisArc2D);
			if (thisToAnchor == null)
				thisToAnchor = thisArc2D.getEndPoint();

			// adjust arc ends to anchors
			if (thisArc2D.getAngleExtent() >= 0.)
				thisArc2D.setAngles(thisFromAnchor, thisToAnchor);
			else
				thisArc2D.setAngles(thisToAnchor, thisFromAnchor);

			// draw
			drawArc(thisArc2D, thisFromAnchor, thisToAnchor, thisStyle);

			// image
			if (thisImage != null)
				drawImage(thisImage, getMidArc(thisArc2D));

			// ends
			drawEdgeEnds(thisFromAnchor, thisToAnchor, thisArc2D, thisStyle);

			// draw edge label
			if (!isBorder && thisLabel != null && !thisLabel.isEmpty())
			{
				// fit
				thisLabel = mangleString(thisLabel, thisFromAnchor, thisToAnchor);
				if (thisLabel == null)
					return;

				// mid arc
				Point2D thisMidArc = getMidArc(thisArc2D);

				// tangent
				double thisTangent = getTangent(thisArc2D, thisMidArc);

				// draw text
				drawText(thisLabel, thisMidArc, thisTangent);
			}
		}
	}

	/**
	 * Draw arc2D
	 * 
	 * @param thisArc2D
	 *        arc
	 */
	private void drawArc(Arc2D thisArc2D, Point2D thisFromAnchor, Point2D thisToAnchor, int thisStyle)
	{
		Graphics2D thisGraphics = (Graphics2D) theGraphics;
		if ((thisStyle & IEdge.STROKEMASK) != 0)
		{
			Stroke thatStroke = thisGraphics.getStroke();
			Stroke thisStroke;
			if ((thisStyle & IEdge.DASH) != 0)
				thisStroke = theDashStroke;
			else if ((thisStyle & IEdge.DOT) != 0)
				thisStroke = theDotStroke;
			else
				thisStroke = null;

			if (thisStroke != null)
			{
				thisGraphics.setStroke(thisStroke);
				thisGraphics.draw(thisArc2D);
				thisGraphics.setStroke(thatStroke);
				return;
			}
		}
		thisGraphics.draw(thisArc2D);
	}

	/**
	 * Draw edge ends
	 * 
	 * @param thisFrom
	 *        from-end
	 * @param thisTo
	 *        to-end
	 * @param thisArc2D
	 *        arc
	 * @param thisStyle
	 *        style code
	 */
	private void drawEdgeEnds(Point2D thisFrom, Point2D thisTo, Arc2D thisArc2D, int thisStyle)
	{
		if (thisStyle == 0)
			return;

		double x1 = thisFrom.getX();
		double y1 = thisFrom.getY();
		double x2 = thisTo.getX();
		double y2 = thisTo.getY();
		double cx = x2 - x1;
		double cy = y2 - y1;

		// do nothing if too near
		double span2 = cx * cx + cy * cy;
		if (span2 < theMinSpanForTerminators)
			return;

		double sx1;
		double sy1;
		double dx1;
		double dy1;
		double sx2;
		double sy2;
		double dx2;
		double dy2;
		if (true || thisArc2D == null)
		{
			double thisOrientation = Math.atan2(y2 - y1, x2 - x1);
			sx1 = theTerminorLength * Math.cos(thisOrientation);
			sy1 = theTerminorLength * Math.sin(thisOrientation);
			dx1 = theTerminatorWidth * Math.cos(thisOrientation + Math.PI / 2);
			dy1 = theTerminatorWidth * Math.sin(thisOrientation + Math.PI / 2);
			sx2 = sx1;
			sy2 = sy1;
			dx2 = dx1;
			dy2 = dy1;
		}
		else
		{
			double thisOrientation1 = getTangent(thisArc2D, thisFrom);
			sx1 = theTerminorLength * Math.cos(thisOrientation1);
			sy1 = theTerminorLength * Math.sin(thisOrientation1);
			dx1 = theTerminatorWidth * Math.cos(thisOrientation1 + Math.PI / 2);
			dy1 = theTerminatorWidth * Math.sin(thisOrientation1 + Math.PI / 2);

			double thisOrientation2 = getTangent(thisArc2D, thisTo);
			sx2 = theTerminorLength * Math.cos(thisOrientation2);
			sy2 = theTerminorLength * Math.sin(thisOrientation2);
			dx2 = theTerminatorWidth * Math.cos(thisOrientation2 + Math.PI / 2);
			dy2 = theTerminatorWidth * Math.sin(thisOrientation2 + Math.PI / 2);
		}

		// from
		switch ((thisStyle >> IEdge.FROMSHIFT) & IEdge.SHAPEMASK)
		{
		case IEdge.TRIANGLE:
		{
			// t
			int x[] = { (int) x1, (int) (x1 + sx1 + dx1), (int) (x1 + sx1 - dx1) };
			int y[] = { (int) y1, (int) (y1 + sy1 + dy1), (int) (y1 + sy1 - dy1) };
			if ((thisStyle & IEdge.FROMSOLID) != 0)
				theGraphics.fillPolygon(x, y, x.length);
			else
			{
				Color thatColor = theGraphics.getColor();
				theGraphics.setColor(theBackColor);
				theGraphics.fillPolygon(x, y, x.length);
				theGraphics.setColor(thatColor);
				theGraphics.drawPolygon(x, y, x.length);
			}
			break;
		}

		case IEdge.CIRCLE:
		{
			// c
			double x = x1 + sx1 / 2 - theTerminorLength / 2;
			double y = y1 + sy1 / 2 - theTerminorLength / 2;
			if ((thisStyle & IEdge.FROMSOLID) != 0)
				theGraphics.fillOval((int) x, (int) y, (int) (theTerminorLength), (int) (theTerminorLength));
			else
			{
				Color thatColor = theGraphics.getColor();
				theGraphics.setColor(theBackColor);
				theGraphics.fillOval((int) x, (int) y, (int) (theTerminorLength), (int) (theTerminorLength));
				theGraphics.setColor(thatColor);
				theGraphics.drawOval((int) x, (int) y, (int) (theTerminorLength), (int) (theTerminorLength));
			}
			break;
		}

		case IEdge.DIAMOND:
		{
			// d
			int x[] = { (int) x1, (int) (x1 + sx1 + dx1), (int) (x1 + sx1 + sx1), (int) (x1 + sx1 - dx1) };
			int y[] = { (int) y1, (int) (y1 + sy1 + dy1), (int) (y1 + sy1 + sy1), (int) (y1 + sy1 - dy1) };
			if ((thisStyle & IEdge.FROMSOLID) != 0)
				theGraphics.fillPolygon(x, y, x.length);
			else
			{
				Color thatColor = theGraphics.getColor();
				theGraphics.setColor(theBackColor);
				theGraphics.fillPolygon(x, y, x.length);
				theGraphics.setColor(thatColor);
				theGraphics.drawPolygon(x, y, x.length);
			}
			break;
		}

		case IEdge.ARROW:
		{
			// a
			int x[] = { (int) (x1 + sx1 + dx1), (int) x1, (int) (x1 + sx1 - dx1) };
			int y[] = { (int) (y1 + sy1 + dy1), (int) y1, (int) (y1 + sy1 - dy1) };
			theGraphics.drawPolyline(x, y, x.length);
			break;
		}
		
		case IEdge.HOOK:
		{
			// h
			int x[] = { (int) (x1 + sx1 + dx1), (int) x1 };
			int y[] = { (int) (y1 + sy1 + dy1), (int) y1 };
			theGraphics.drawPolyline(x, y, x.length);
			break;
		}
		}

		// to
		switch ((thisStyle >> IEdge.TOSHIFT) & IEdge.SHAPEMASK)
		{
		case IEdge.TRIANGLE:
		{
			// t
			int x[] = { (int) x2, (int) (x2 - sx2 + dx2), (int) (x2 - sx2 - dx2) };
			int y[] = { (int) y2, (int) (y2 - sy2 + dy2), (int) (y2 - sy2 - dy2) };
			if ((thisStyle & IEdge.TOSOLID) != 0)
				theGraphics.fillPolygon(x, y, x.length);
			else
			{
				Color thatColor = theGraphics.getColor();
				theGraphics.setColor(theBackColor);
				theGraphics.fillPolygon(x, y, x.length);
				theGraphics.setColor(thatColor);
				theGraphics.drawPolygon(x, y, x.length);
			}
			break;
		}

		case IEdge.CIRCLE:
		{
			// c
			double x = x2 - sx2 / 2 - theTerminorLength / 2;
			double y = y2 - sy2 / 2 - theTerminorLength / 2;
			if ((thisStyle & IEdge.TOSOLID) != 0)
				theGraphics.fillOval((int) x, (int) y, (int) (theTerminorLength), (int) (theTerminorLength));
			else
			{
				Color thatColor = theGraphics.getColor();
				theGraphics.setColor(theBackColor);
				theGraphics.fillOval((int) x, (int) y, (int) (theTerminorLength), (int) (theTerminorLength));
				theGraphics.setColor(thatColor);
				theGraphics.drawOval((int) x, (int) y, (int) (theTerminorLength), (int) (theTerminorLength));
			}
			break;
		}

		case IEdge.DIAMOND:
		{
			// d
			int x[] = { (int) x2, (int) (x2 - sx2 + dx2), (int) (x2 - sx2 - sx2), (int) (x2 - sx2 - dx2) };
			int y[] = { (int) y2, (int) (y2 - sy2 + dy2), (int) (y2 - sy2 - sy2), (int) (y2 - sy2 - dy2) };
			if ((thisStyle & IEdge.TOSOLID) != 0)
				theGraphics.fillPolygon(x, y, x.length);
			else
			{
				Color thatColor = theGraphics.getColor();
				theGraphics.setColor(theBackColor);
				theGraphics.fillPolygon(x, y, x.length);
				theGraphics.setColor(thatColor);
				theGraphics.drawPolygon(x, y, x.length);
			}
			break;
		}

		case IEdge.ARROW:
		{
			// a
			int x[] = { (int) (x2 - sx2 + dx2), (int) x2, (int) (x2 - sx2 - dx2) };
			int y[] = { (int) (y2 - sy2 + dy2), (int) y2, (int) (y2 - sy2 - dy2) };
			theGraphics.drawPolyline(x, y, x.length);
			break;
		}

		case IEdge.HOOK:
		{
			// h
			int x[] = { (int) (x2 - sx2 + dx2), (int) x2 };
			int y[] = { (int) (y2 - sy2 + dy2), (int) y2 };
			theGraphics.drawPolyline(x, y, x.length);
			break;
		}
		}
	}

	/**
	 * Convert Arc to Arc2D
	 * 
	 * @param thisArc
	 *        arc
	 * @return arc
	 */
	private Arc2D toArc2D(Arc thisArc)
	{
		double x1 = xUnitCircleToView(thisArc.x);
		double y1 = yUnitCircleToView(thisArc.y);
		double x2 = xUnitCircleToView(thisArc.x - thisArc.r);
		double y2 = yUnitCircleToView(thisArc.y - thisArc.r);
		double thisStart = Math.toDegrees(-thisArc.start);
		if (thisStart < 0.)
			thisStart += 360.;
		double thisExtent = Math.toDegrees(-thisArc.angle);
		Arc2D.Double thisArc2D = new Arc2D.Double();
		thisArc2D.setFrameFromCenter(x1, y1, x2, y2);
		thisArc2D.setAngleStart(thisStart);
		thisArc2D.setAngleExtent(thisExtent);
		thisArc2D.setArcType(Arc2D.OPEN);
		return thisArc2D;
	}

	// D R A W . A R C . T E X T

	/**
	 * Get arc eccentricity
	 * 
	 * @param thisArc2D
	 *        arc
	 * @return eccentricity of arc
	 */
	static private double getEccentricity(Arc2D thisArc2D)
	{
		double a = thisArc2D.getWidth() / 2.;
		double b = thisArc2D.getHeight() / 2.;
		double d = a > b ? (b * b) / (a * a) : (a * a) / (b * b);
		return Math.sqrt(1 - d);
	}

	/**
	 * Get mid-arc point
	 * 
	 * @param thisArc2D
	 *        arc
	 * @return point at mid-arc
	 */
	private Point2D getMidArc(Arc2D thisArc2D)
	{
		double a = thisArc2D.getWidth() / 2.;
		double b = thisArc2D.getHeight() / 2.;
		double theta = Math.toRadians(-thisArc2D.getAngleStart()) + Math.toRadians(-thisArc2D.getAngleExtent() / 2.);
		double x = a * Math.cos(theta);
		double y = b * Math.sin(theta);
		return new Point2D.Double(x + thisArc2D.getCenterX(), y + thisArc2D.getCenterY());
	}

	/**
	 * Get tangent to this Arc2D at given point
	 * 
	 * @param thisArc2D
	 *        arc
	 * @param thisWhere
	 *        point on arc
	 * @return tangent of this arc at given point
	 */
	private double getTangent(Arc2D thisArc2D, Point2D thisWhere)
	{
		// center, eccentricity, major axis, minor axis
		double x = thisWhere.getX() - thisArc2D.getCenterX();
		double y = thisWhere.getY() - thisArc2D.getCenterY();
		double e = getEccentricity(thisArc2D);
		double a = thisArc2D.getWidth() / 2.;
		double b = thisArc2D.getHeight() / 2.;

		// angles between foci and point
		double thisAngle1;
		double thisAngle2;
		if (a >= b)
		{
			double ea = e * a;
			thisAngle1 = Math.atan2(y, x - ea);
			thisAngle2 = Math.atan2(y, x + ea);
		}
		else
		{
			double eb = e * b;
			thisAngle1 = Math.atan2(y - eb, x);
			thisAngle2 = Math.atan2(y + eb, x);
		}
		// tangent
		double thisBissector = (thisAngle1 + thisAngle2) / 2.;
		return thisBissector + Math.PI / 2.;
	}

	/**
	 * Draw text
	 * 
	 * @param thisString
	 *        string to be drawn
	 * @param thisWhere
	 *        where to put text (centered on this point)
	 * @param thisOrientation
	 *        text orientation
	 */
	private void drawText(String thisString, Point2D thisWhere, double thisOrientation)
	{
		Graphics2D thisGraphics = (Graphics2D) theGraphics;

		// save current transform
		AffineTransform thatTransform = thisGraphics.getTransform();

		// font metrics
		FontMetrics thisFontMetrics = thisGraphics.getFontMetrics();
		int thisWidth = thisFontMetrics.stringWidth(thisString);

		// text orientation
		boolean reverse = thisOrientation > Math.PI / 2.;
		int thisYShift = 0;
		if (reverse)
		{
			thisOrientation += Math.PI;
			thisYShift = -thisFontMetrics.getAscent();
		}
		else
		{
			thisYShift = thisFontMetrics.getDescent();
		}

		// translate to center of text
		AffineTransform thisTransform = new AffineTransform(thatTransform);
		thisTransform.translate(thisWhere.getX(), thisWhere.getY());
		thisTransform.rotate(thisOrientation);
		thisGraphics.setTransform(thisTransform);
		thisGraphics.drawString(thisString, -thisWidth / 2, -thisYShift);

		// restore transform
		thisGraphics.setTransform(thatTransform);
	}

	/**
	 * Draw text from (x1,y1) to (x2,y2)
	 * 
	 * @param thisString
	 *        text
	 * @param thisFrom
	 *        from-point
	 * @param thisTo
	 *        to-point
	 */
	private void drawText(String thisString, Point2D thisFrom, Point2D thisTo)
	{
		double x1 = thisFrom.getX();
		double y1 = thisFrom.getY();
		double x2 = thisTo.getX();
		double y2 = thisTo.getY();

		// orientation
		double thisOrientation = Math.atan2(y1 - y2, x1 - x2);
		if (thisOrientation < 0)
			thisOrientation += Math.PI;

		// where
		Point2D thisWhere = new Point2D.Double((x2 + x1) / 2., (y2 + y1) / 2.);

		// draw
		drawText(thisString, thisWhere, thisOrientation);
	}

	/**
	 * Mangle string to fit in
	 * 
	 * @param thisString
	 * @param thisFrom
	 *        from-point
	 * @param thisTo
	 *        to-point
	 * @return mangled string or null
	 */
	private String mangleString(String thisString, Point2D thisFrom, Point2D thisTo)
	{
		double cx = thisTo.getX() - thisFrom.getX();
		double cy = thisTo.getY() - thisFrom.getY();
		int span = (int) Math.sqrt(cx * cx + cy * cy) - theTextPadding;

		// label font size
		FontMetrics fm = theGraphics.getFontMetrics();
		int w = fm.stringWidth(thisString);

		// truncate label
		if (w > span)
		{
			// compute average character width
			int wunit = fm.stringWidth("x");

			// compute trailing dots width
			int wdots = fm.stringWidth("...");

			// compute number of characters that fit before dots
			int thisNChars = (span - wdots) / wunit;

			// ensure at least one
			if (thisNChars < 1)
				thisNChars = 1;

			// perform truncation if we actually truncate
			int thisLen = thisString.length();
			if (thisLen > thisNChars)
				thisString = thisString.substring(0, thisNChars) + "...";
		}
		return thisString;
	}

	// D R A W . L I N E

	/**
	 * Draw line from p1 to p2
	 * 
	 * @param thisFromPoint
	 *        from-point
	 * @param thisToPoint
	 *        to-point
	 */
	private void drawLine(Point2D thisFromPoint, Point2D thisToPoint, int thisStyle)
	{
		if ((thisStyle & IEdge.STROKEMASK) != 0)
		{
			Graphics2D thisGraphics = (Graphics2D) theGraphics;
			Stroke thatStroke = thisGraphics.getStroke();
			Stroke thisStroke;
			if ((thisStyle & IEdge.DASH) != 0)
				thisStroke = theDashStroke;
			else if ((thisStyle & IEdge.DOT) != 0)
				thisStroke = theDotStroke;
			else
				thisStroke = null;

			if (thisStroke != null)
			{
				thisGraphics.setStroke(thisStroke);
				theGraphics.drawLine((int) thisFromPoint.getX(), (int) thisFromPoint.getY(), (int) thisToPoint.getX(), (int) thisToPoint.getY());
				thisGraphics.setStroke(thatStroke);
				return;
			}
		}
		theGraphics.drawLine((int) thisFromPoint.getX(), (int) thisFromPoint.getY(), (int) thisToPoint.getX(), (int) thisToPoint.getY());
	}

	// D R A W . I M A G E

	/**
	 * Draw image at point
	 * 
	 * @param thisImage
	 *        image
	 * @param where
	 *        location
	 */
	private void drawImage(Image thisImage, Point2D where)
	{
		if (thisImage != null)
		{
			int hi2 = thisImage.getHeight(null) / 2;
			int wi2 = thisImage.getWidth(null) / 2;
			int x = (int) where.getX() - wi2;
			int y = (int) where.getY() - hi2;
			theGraphics.drawImage(thisImage, x, y, null);
		}
	}

	/**
	 * Get middle
	 * 
	 * @param x1
	 *        from point
	 * @param x2
	 *        to mpoint
	 * @return middle
	 */
	private Point2D getMiddle(Point2D x1, Point2D x2)
	{
		double x = (x1.getX() + x2.getX()) / 2.0;
		double y = (x1.getY() + x2.getY()) / 2.0;
		return new Point2D.Double(x, y);
	}

	// D R A W . N O D E S P A C E

	/**
	 * Draw node's space
	 * 
	 * @param thisNode
	 *        node
	 */
	private void drawSpace(INode thisNode)
	{
		// color
		Color thisBackColor = thisNode.getBackColor();
		if (thisBackColor == null)
		{
			thisBackColor = theNodeBackColor;
		}
		// draw
		Location thisLocation = thisNode.getLocation();
		drawCircle(thisLocation.euclidian.center.re, thisLocation.euclidian.center.im, thisLocation.euclidian.radius, thisBackColor);
	}

	/**
	 * Draw circle
	 * 
	 * @param x
	 *        center x-coordinate
	 * @param y
	 *        center y-coordinate
	 * @param r
	 *        radius
	 * @param thisColor
	 *        color
	 */
	private void drawCircle(double x, double y, double r, Color thisColor)
	{
		theGraphics.setColor(thisColor);
		theGraphics.drawOval(xUnitCircleToView(x - r), yUnitCircleToView(y - r), wUnitCircleToView(2 * r), hUnitCircleToView(2 * r));
	}

	// I N T E R S E C T I O N

	/**
	 * Get intersection between line and rectangle
	 * 
	 * @param thisRect
	 *        rectangle
	 * @param thisFrom
	 *        from-point on line
	 * @param thisTo
	 *        to-point on line
	 * @return intersection point
	 */
	private Point2D getIntersection(Rectangle2D thisRect, Point2D thisFrom, Point2D thisTo)
	{
		if (thisRect == null)
			return null;

		int thisCode = thisRect.outcode(thisFrom);

		// rectangle
		double x0 = thisRect.getCenterX();
		double y0 = thisRect.getCenterY();
		double x = thisRect.getX();
		double y = thisRect.getY();
		double w = thisRect.getWidth();
		double h = thisRect.getHeight();

		// points on top, bottom, left, right
		double ty = y;
		double by = y + h;
		double lx = x;
		double rx = x + w;

		// line
		double tanAlpha = (thisTo.getY() - thisFrom.getY()) / (thisTo.getX() - thisFrom.getX());

		// drawPoint((ty - y0) / tanAlpha + x0, ty, Color.MAGENTA);
		// drawPoint((by - y0) / tanAlpha + x0, by, Color.ORANGE);
		// drawPoint(lx, (lx - x0) * tanAlpha + y0, Color.BLUE);
		// drawPoint(rx, (rx - x0) * tanAlpha + y0, Color.CYAN);
		// drawLine(thisFrom, thisTo);

		if ((thisCode & Rectangle2D.OUT_TOP) != 0)
		{
			// compute top intersection
			double tx = (ty - y0) / tanAlpha + x0;
			if (tx >= lx && tx <= rx)
			{
				return new Point2D.Double(tx, ty);
			}
		}
		if ((thisCode & Rectangle2D.OUT_BOTTOM) != 0)
		{
			// compute bottom intersection
			double bx = (by - y0) / tanAlpha + x0;
			if (bx >= lx && bx <= rx)
			{
				return new Point2D.Double(bx, by);
			}
		}
		if ((thisCode & Rectangle2D.OUT_LEFT) != 0)
		{
			// compute left intersection
			double ly = (lx - x0) * tanAlpha + y0;
			if (ly >= ty && ly <= by)
			{
				return new Point2D.Double(lx, ly);
			}
		}
		if ((thisCode & Rectangle2D.OUT_RIGHT) != 0)
		{
			// compute right intersection
			double ry = (rx - x0) * tanAlpha + y0;
			if (ry >= ty && ry <= by)
			{
				return new Point2D.Double(rx, ry);
			}
		}
		return null;
	}

	/**
	 * Get whether boxes intersect (boxes have to be infalted by one pixel)
	 * 
	 * @param thisBox1
	 *        box1
	 * @param thisBox2
	 *        box2
	 * @return true if nodes' boxes intersect
	 */
	private boolean boxesIntersect(Rectangle2D thisBox1, Rectangle2D thisBox2)
	{
		if (thisBox1 != null && thisBox2 != null)
		{
			// inflate
			Rectangle2D thisFromBox2 = new Rectangle2D.Double();
			thisFromBox2.setFrame(new Point2D.Double(thisBox1.getMinX() - 1, thisBox1.getMinY() - 1), new Dimension((int) thisBox1.getWidth() + 2, (int) thisBox1.getHeight() + 2));
			Rectangle2D thisToBox2 = new Rectangle2D.Double();
			thisToBox2.setFrame(new Point2D.Double(thisBox2.getMinX() - 1, thisBox2.getMinY() - 1), new Dimension((int) thisBox2.getWidth() + 2, (int) thisBox2.getHeight() + 2));

			// intersection test
			if (thisFromBox2.intersects(thisToBox2))
				return true;
		}
		return false;
	}

	/**
	 * Get intersection between arc and rectangle
	 * 
	 * @param thisRect
	 *        rectangle
	 * @param thisArc
	 *        arc
	 * @return intersection point
	 */
	private Point2D getIntersection(Rectangle2D thisRect, Arc2D thisArc)
	{
		if (thisRect == null)
			return null;

		// rectangle
		double x = thisRect.getCenterX();
		double y = thisRect.getCenterY();
		double w = thisRect.getWidth() / 2.;
		double h = thisRect.getHeight() / 2.;

		// arc
		double ax = thisArc.getCenterX();
		double ay = thisArc.getCenterY();
		double a = thisArc.getWidth() / 2.;
		double b = thisArc.getHeight() / 2.;
		double a2 = a * a;
		double b2 = b * b;

		// rectangle center relative to arc center
		double drx = x - ax;
		double dry = y - ay;
		boolean isSouth = dry < 0.;
		boolean isEast = drx < 0.;

		// rectangle top, bottom, left, right relative to arc center
		double drl = drx - w;
		double drr = drx + w;
		double drt = dry - h;
		double drb = dry + h;

		// points on top, bottom, left, right
		double ty = dry - h;
		double by = dry + h;
		double lx = drx - w;
		double rx = drx + w;
		double k;

		// compute top intersection
		k = (ty * ty) / b2;
		if (k <= 1.)
		{
			double tx = Math.sqrt((1. - k) * a2);
			if (isEast)
				tx = -tx;
			// if other coodinate is on rectangle
			if (tx >= drl && tx <= drr)
			{
				if (isOnArc(tx, ty, thisArc))
					return new Point2D.Double(tx + ax, ty + ay);
			}
		}

		// compute bottom intersection
		k = (by * by) / b2;
		if (k <= 1.)
		{
			double bx = Math.sqrt((1. - k) * a2);
			if (isEast)
				bx = -bx;
			// if other coodinate is on rectangle
			if (bx >= drl && bx <= drr)
			{
				if (isOnArc(bx, by, thisArc))
					return new Point2D.Double(bx + ax, by + ay);
			}
		}

		// compute left intersection
		k = (lx * lx) / a2;
		if (k <= 1.)
		{
			double ly = Math.sqrt((1. - k) * b2);
			if (isSouth)
				ly = -ly;
			// if other coodinate is on rectangle
			if (ly >= drt && ly <= drb)
			{
				if (isOnArc(lx, ly, thisArc))
					return new Point2D.Double(lx + ax, ly + ay);
			}
		}

		// compute right intersection
		k = (rx * rx) / a2;
		if (k <= 1.)
		{
			double ry = Math.sqrt((1. - k) * b2);
			if (isSouth)
				ry = -ry;
			// if other coodinate is on rectangle
			if (ry >= drt && ry <= drb)
			{
				if (isOnArc(rx, ry, thisArc))
					return new Point2D.Double(rx + ax, ry + ay);
			}
		}
		return null;
	}

	// O N . A R C

	/**
	 * Test whether point is on arc
	 * 
	 * @param dx
	 *        x-offset from arc center
	 * @param dy
	 *        y-offset from arc center
	 * @param thisArc
	 *        arc
	 * @return whether the point is on arc
	 */
	private boolean isOnArc(double dx, double dy, Arc2D thisArc)
	{
		double a = pointToAngle(dx, dy, thisArc);
		return thisArc.containsAngle(Math.toDegrees(a));
	}

	/**
	 * Compute angle for point
	 * 
	 * @param dx
	 *        x-offset from arc center
	 * @param dy
	 *        y-offset from arc center
	 * @param thisArc
	 *        arc
	 * @return computed angle
	 */
	private double pointToAngle(double dx, double dy, Arc2D thisArc)
	{
		double thisResult = Math.atan2(-dy * thisArc.getWidth(), dx * thisArc.getHeight());
		return thisResult;
	}
}
